package com.tianyuan.test1;

import java.util.HashMap;
import java.util.Map;
/**
 * 哈希
 */

/**
 * 两数之和
 *
 * @date 2025/10/25 20:48
 * 给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。
 * 你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
 * 你可以按任意顺序返回答案。
 *
 * 示例 1：
 * 输入：nums = [2,7,11,15]，target = 9
 * 输出：[0,1]
 * 解释：因为 nums [0] + nums [1] == 9，返回 [0, 1]。
 * 示例 2：
 * 输入：nums = [3,2,4]，target = 6
 * 输出：[1,2]
 * 示例 3：
 * 输入：nums = [3,3]，target = 6
 * 输出：[0,1]
 */


public class Solution {
    /**
     * 查找数组中两个元素之和等于目标值的索引
     * @param nums 输入的整数数组
     * @param target 目标和
     * @return 两个元素的索引组成的数组（按出现顺序返回）
     * @throws IllegalArgumentException 当不存在满足条件的两个元素时抛出
     */
    public int[] twoSum(int[] nums, int target) {
        // 创建哈希表，用于存储数组元素的值和对应的索引（键：元素值，值：元素索引）
        Map<Integer, Integer> map = new HashMap<>();
        // 遍历数组中的每个元素
        for (int i = 0; i < nums.length; i++) {
            // 计算与当前元素配对后能得到目标值的“互补数”
            int complement = target - nums[i];
            // 检查哈希表中是否存在这个互补数
            if (map.containsKey(complement)) {
                // 若存在，说明之前遍历过的元素中已有与当前元素配对的解
                // 返回互补数的索引（之前存储的）和当前元素的索引
                return new int[]{map.get(complement), i};
            }
            // 若不存在互补数，将当前元素的值和索引存入哈希表，供后续元素查找
            map.put(nums[i], i);
        }
        // 遍历完数组仍未找到解时，抛出异常
        throw new IllegalArgumentException("No two sum solution");
    }
    /**
     * 思路
     * 标签：哈希映射
     * 这道题本身如果通过暴力遍历的话也是很容易解决的，时间复杂度在 O(n2)
     * 由于哈希查找的时间复杂度为 O(1)，所以可以利用哈希容器 map 降低时间复杂度
     * 遍历数组 nums，i 为当前下标，每个值都判断map中是否存在 target-nums[i] 的 key 值
     * 如果存在则找到了两个值，如果不存在则将当前的 (nums[i],i) 存入 map 中，继续遍历直到找到为止
     * 如果最终都没有结果则抛出异常
     */
    /**
     * 1.先有map
     * 2.for循环数组
     * 找到每个值的互补数
     *   if判断map中有没有互补数
     *   有就返回两个索引数组
     *   无就添加这个值和其索引到map
     * 3.遍历完还没有就抛异常
     */






    public static void main(String[] args) {
        Solution solution = new Solution();

        // 示例1：nums = [2,7,11,15]，target = 9
        int[] nums1 = {2, 7, 11, 15};
        int target1 = 9;
        int[] result1 = solution.twoSum(nums1, target1);
        System.out.println("示例1：");
        System.out.println("输入：nums = [2,7,11,15]，target = 9");
        System.out.println("输出：[" + result1[0] + "," + result1[1] + "]");
        System.out.println("解释：因为 nums[0] + nums[1] = " + nums1[0] + " + " + nums1[1] + " = " + target1 + "，返回 [" + result1[0] + "," + result1[1] + "]");
        System.out.println();

        // 示例2：nums = [3,2,4]，target = 6
        int[] nums2 = {3, 2, 4};
        int target2 = 6;
        int[] result2 = solution.twoSum(nums2, target2);
        System.out.println("示例2：");
        System.out.println("输入：nums = [3,2,4]，target = 6");
        System.out.println("输出：[" + result2[0] + "," + result2[1] + "]");
        System.out.println("解释：因为 nums[1] + nums[2] = " + nums2[1] + " + " + nums2[2] + " = " + target2 + "，返回 [" + result2[0] + "," + result2[1] + "]");
        System.out.println();

        // 示例3：nums = [3,3]，target = 6
        int[] nums3 = {3, 3};
        int target3 = 6;
        int[] result3 = solution.twoSum(nums3, target3);
        System.out.println("示例3：");
        System.out.println("输入：nums = [3,3]，target = 6");
        System.out.println("输出：[" + result3[0] + "," + result3[1] + "]");
        System.out.println("解释：因为 nums[0] + nums[1] = " + nums3[0] + " + " + nums3[1] + " = " + target3 + "，返回 [" + result3[0] + "," + result3[1] + "]");
    }
}
